import org.junit.jupiter.api.DisplayName;
import org.junit.jupiter.params.ParameterizedTest;
import org.junit.jupiter.params.provider.Arguments;
import org.junit.jupiter.params.provider.MethodSource;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.stream.Stream;

/**
 * 查找和替换模式
 * 题目：你有一个单词列表words和一个模pattern，你想知道 words 中的哪些单词与模式匹配。
 * 如果存在字母的排列 p，使得将模式中的每个字母 x 替换为 p(x) 之后，我们就得到了所需的单词，那么单词与模式是匹配的。
 * （回想一下，字母的排列是从字母到字母的双射：每个字母映射到另一个字母，没有两个字母映射到同一个字母。）
 * 返回 words 中与给定模式匹配的单词列表。
 * 你可以按任何顺序返回答案。
 * <p>
 * 示例：
 * 输入：words = ["abc","deq","mee","aqq","dkd","ccc"], pattern = "abb"
 * 输出：["mee","aqq"]
 * <p>
 * 解释：
 * "mee" 与模式匹配，因为存在排列 {a -> m, b -> e, ...}。
 * "ccc" 与模式不匹配，因为 {a -> c, b -> c, ...} 不是排列。
 * 因为 a 和 b 映射到同一个字母。
 * <p>
 * 提示：
 * 1 <= words.length <= 50
 * 1 <= pattern.length = words[i].length<= 20
 * <p>
 * 来源：力扣（LeetCode-890）
 * 链接：https://leetcode-cn.com/problems/find-and-replace-pattern
 *
 * @author godfrey
 * @since 2020-10-29
 */
@DisplayName("查找和替换模式")
public class FindAndReplacePattern {

    static Stream<Arguments> testArguments() {
        return Stream.of(
                Arguments.arguments(new String[]{"abc", "deq", "mee", "aqq", "dkd", "ccc"}, "abb")
        );
    }

    @DisplayName("双射-时间复杂度：O(n),空间复杂度：O(n)")
    @ParameterizedTest
    @MethodSource("testArguments")
    void findAndReplacePattern(String[] words, String pattern) {
        int n = pattern.length();
        List<String> results = new ArrayList<>();
        for (String word : words) {
            if (word.length() != pattern.length()) {
                continue;
            }
            Map<Character, Character> map = new HashMap<>();
            int i;
            for (i = 0; i < n; ++i) {
                char c1 = word.charAt(i);
                char c2 = pattern.charAt(i);
                //判断有无key
                if (map.containsKey(c1)) {
                    //有key，判断value是否同一个
                    if (map.get(c1) != c2) {
                        break;
                    }
                    //无key,判断有无value
                } else if (map.containsValue(c2)) {
                    //有value
                    break;
                    //无value
                } else {
                    map.put(c1, c2);
                }
            }
            if (i == n) {
                results.add(word);
            }
        }
        System.out.println(results);
    }
}
